use std::fmt::Debug;

// 冒泡排序
pub fn bubble_sort<T>(arr: &mut [T])
    where T: Ord + Debug {
    let len = arr.len();
    for i in 0..(len - 2) {
        for j in 0..(len - i - 1) {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

// 插入排序
pub fn selection_sort<T>(arr: &mut [T])
    where T: Ord + Debug {
    let len = arr.len();
    for left_index in 0..(len - 1) {
        let mut small_index = left_index;
        for right_index in (left_index + 1)..len {
            if arr[small_index] > arr[right_index] {
                small_index = right_index;
            }
        }
        arr.swap(left_index, small_index);
    }
}

// 未知排序，类似冒泡排序
pub fn unknown_sort<T>(arr: &mut [T])
    where T: Ord + Debug {
    let len = arr.len();
    for i in 0..(len - 1) {
        for j in (i + 1)..len {
            if arr[i] > arr[j] {
                arr.swap(i, j);
            }
        }
    }
}

// 快速排序
pub fn quick_sort<T>(arr: &mut Vec<T>)
    where T: Ord + Copy + Debug {
    q_sort(arr, 0, arr.len() - 1);
}

// 快速排序
fn q_sort<T>(arr: &mut Vec<T>, left: usize, right: usize)
    where T: Ord + Copy + Debug {
    if left < right {
        let x = arr[left];
        let mut i = left;
        let mut j = right;
        while i < j {
            while i < j && arr[j] > x {
                j -= 1;
            }
            if i < j {
                arr.swap(i, j);
            }
            while i < j && arr[i] < x {
                i += 1;
            }
            if i < j {
                arr.swap(i, j);
            }
        }
        arr[i] = x;
        q_sort(arr, left, i - 1);
        q_sort(arr, i + 1, right);
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}
